package com.base.binarytree;

import jdk.nashorn.internal.runtime.regexp.joni.exception.ValueException;

import java.util.HashMap;
import java.util.Map;

/**
 * @ClassName BuildTree2
 * @Description 106. 从中序与后序遍历序列构造二叉树
 * 根据一棵树的中序遍历与后序遍历构造二叉树。
 *
 * 注意:
 * 你可以假设树中没有重复的元素。
 * 思路同于105题
 * @Author li
 * Date 2021/9/7 18:49
 * Copyright
 **/
public class BuildTree2 {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int inLen = inorder.length;
        int postLen = postorder.length;
        if (postLen == 0){
            return null;
        }
        if (postLen != inLen){
            throw new ValueException("值错误");
        }
        // 将中序遍历的值存在哈希表中，方便查询
        Map<Integer,Integer> map = new HashMap<>(inLen);
        for (int i = 0; i < inLen; i++) {
            map.put(inorder[i],i);
        }
        return buildTree(postorder,0,postLen-1,map,0,inLen-1);

    }
    public TreeNode buildTree(int[] postorder,int postStart,int postEnd,Map<Integer,Integer> map,int inStart,int inEnd){
        if (postStart > postEnd){
            return null;
        }
        int cur = postorder[postEnd];
        TreeNode root = new TreeNode(cur);
        root.left = buildTree(postorder,postStart,postStart+map.get(cur)-inStart-1,map,inStart,map.get(cur)-1);
        root.right = buildTree(postorder,postStart+map.get(cur)-inStart,postEnd-1,map,map.get(cur)+1,inEnd);
        return root;
    }
}
